Método de Deducción Paso a Paso Estructuras Discretas Departamento de Ingenería en Computación
Introducción
¿Cuántas veces te has quedado con las ganas de demostrar la validez de tus ideas ante tu grupo de amigos, pero por carecer de una forma clara y concisa de hacerlo no lo has logrado y te sientes frustrado? ¿En cuántas situaciones quisiste resolver un problema, pero no lo lograste debido a que no sabías cómo estructurar las ideas? ¿Has estado ante una situación confusa que al parecer no tiene solución? ¿Qué haces para demostrar que tu solución basada en una argumentación es válida? Y surge otra pregunta: ¿por qué es importante demostrar que un razonamiento es válido?
En la presente unidad revisarás elementos suficientes para demostrar la validez de tus argumentos haciendo uso de reglas de inferencia. Para ello es importante el estudio de la lógica, pues te ayuda a estructurar tu pensamiento, es decir, en cómo pensar (no tanto en qué pensar).
Cuando realices alguna investigación, pretendas demostrar una idea, desarrolles una tesis o tengas que probar algún producto de software, en fin, cuando desees convencer a tus amigos de que tu idea es válida, tendrás que usar algún método de la lógica proposicional.
Objetivo
Demostrarás la validez de un argumento o razonamiento haciendo uso del método de deducción paso a paso (MDPP) aplicado a la lógica proposicional.
Se dice que el objetivo de la lógica es proporcionar reglas de inferencia que permitan demostrar la validez de un razonamiento. Para hablar de un razonamiento es necesario hacer referencia a un argumento. Para hablar de un argumento es imprescindible precisar las hipótesis y la conclusión que lo integran.
Ahora bien, las hipótesis y la conclusión deben ser fórmulas proposicionales. Surge entonces la pregunta: ¿qué es una fórmula proposicional? Empezarás por conocer la definición de proposición.
Una proposición es un enunciado declarativo que puede adquirir el valor de falso o verdadero.
Pero surge otra pregunta: ¿cuáles son los tipos de enunciados que existen? En general, se clasifican en:
Están relacionados con órdenes, mandatos o exhortos, pero también pueden indicar alguna petición o ruego: “¡comes y te vas!”, “¡silencio!”, “¡perdóname!”.
También son conocidos como enunciativos. Expresan una idea, afirman o niegan algo, sirven para comunicar: “la casa es roja”, “Jorge estudia estructuras discretas”, “2 + 5 = 7”.
Trabajarás únicamente con enunciados declarativos.
Los fundamentos de la lógica proposicional clasifican las fórmulas proposicionales en tautologías, contradicciones y contingencias, con base en la generación de tablas de verdad. También puedes obtener ciertas equivalencias y formas normales principales empleando una serie de reglas y propiedades.
Ha llegado el momento de demostrar la validez de un razonamiento. Para esto existen algunos métodos; el más sencillo consiste en establecer una relación entre las hipótesis y la conclusión por medio de tablas de verdad, pero es un método que suele presentar ciertas restricciones. Así que ahora es el momento de que aprendas un nuevo método.
El método de deducción paso a paso
Para usar el método de deducción paso a paso (MDPP), es necesario que pases el argumento o razonamiento dado en lenguaje natural a lógica simbólica. De esta manera, todas las hipótesis y la conclusión deberán estar escritos en notación simbólica.
Sirve para meter una premisa o hipótesis en cualquier paso de la deducción. Si tienes cinco premisas, significa que debes usar al menos cinco veces la regla P para poder meter todas las hipótesis. “Al menos cinco veces”: esto quiere decir que puedes meter una premisa más de una vez. ¿Está claro?
Surge otra pregunta: ¿cuál hipótesis debes meter primero? No importa cuál hipótesis metas primero, pero te sugiero que sea aquélla que menos se parezca a la conclusión, esto significa que no contengan una atómica en común. Sin embargo, puedes meter la hipótesis que quieras.
Ahora bien, puedes meter una siguiente hipótesis. En este caso debe ser aquélla que se parezca en algo a la que ya tienes, tal vez alguna atómica en común. Aquí sí debes tener cuidado con la hipótesis que metas.
Sirve para implicar tautológicamente una o varias expresiones obtenidas en algún paso de la deducción y para encontrar expresiones equivalentes. Esto significa que puedes obtener alguna equivalencia de lo que ya tienes en algún paso de la deducción. Las equivalencias se obtienen por el método algebraico. La expresión Eq corresponde a una equivalencia.
¿Para qué te sirve obtener equivalencias? La pregunta es muy interesante, pero la respuesta lo es más.
Recuerda que debes implicar las hipótesis o las expresiones equivalentes que obtengas, para ello utiliza alguna de las 14 implicaciones que aparecen en la tabla III.
En varias ocasiones te darás cuenta de que es necesario obtener expresiones equivalentes para que éstas se parezcan a alguna de las implicaciones tautológicas que aparecen en la tabla. Por otra parte, es indispensable que realices una instancia de sustitución para que uses una de las implicaciones. ¿Y qué es una instancia de sustitución?
Supón que deseas usar la I11 que dice lo siguiente:
I11 P, P → Q Q
Si tienes dos fórmulas proposicionales dadas por:
A ∨ B
7B ∧ 7C
Entonces procedes de la siguiente manera; escribes:
I11 P, P → Q Q
La instancia de sustitución opera únicamente sobre atómicas. Entonces sustituyes la atómica P por A ∨ B, tantas veces como P aparezca en la expresión; y en lugar de Q escribes 7B ∧ 7C, del siguiente modo:
I11 P, P → Q Q
(A ∨ B), (A ∨ B) → (7B ∧ 7C) (7B ∧ 7C)
Ahora surge la pregunta: ¿cómo sabes que lo que hiciste estuvo bien? Recuerda que cada implicación tautológica es una tautología, entonces, lo que obtengas al hacer la instancia de sustitución debe ser una tautología. Construye la tabla de verdad para verificarlo.
Aclaraciones:
Antes de que construyas la tabla de verdad de I11, recuerda que no es un conectivo, sino un símbolo. Para generar la tabla de verdad se sustituyó el símbolo por el conectivo →. Lo mismo pasó con la instancia de sustitución.
Cuando aparezca una coma (,) en la implicación, significa que para obtener la tabla de verdad debes cambiar este símbolo por conjunción (∧).
Si consideras lo siguiente:
antecedente consecuente
Significa que todas las hipótesis aparecen en el antecedente y que la conclusión se encuentra en el consecuente.
Por otra parte, todas las hipótesis se relacionan con una conjunción. Sustituye el símbolo por una condicional → y procede con el resto. Así, tu expresión queda de la siguiente manera:
H1 ∧ H2 ∧ H3 ∧ ... ∧ Hn C
Esta expresión debe corresponder a una tautología.
Lo vas a demostrar construyendo la tabla de verdad correspondiente, por medio de la cual verás que corresponde a una tautología.
Entonces procede a construir la tabla de verdad.
Construye la tabla de verdad de la I11
P Q
((P) ∧ (P → Q)) → P
T T
T
T
T
T F
F
T
T
F T
F
T
F
F F
F
T
F
Al revisar la columna resultante, te das cuenta de que la fórmula proposicional corresponde a una tautología. ¿Por qué es una tautología? Porque la columna resultante contiene únicamente valores verdaderos.
1
Construye la tabla de verdad de la instancia de sustitución correspondiente a I11:
A B C
((A ∨ B) ∧ ((A ∨ B)→(7B ∧ 7C))) → (7B ∧ 7C)
T T T
F
T
F
T T F
F
T
F
T F T
F
T
F
T F F
F
T
F
F T T
F
T
F
F T F
F
T
F
F F T
F
T
F
F F F
F
T
F
Como ya viste, lo obtenido a partir de la instancia de sustitución corresponde a una tautología; por lo tanto, estás en lo correcto.
2
Seguimos con la explicación del método
Cuando metas alguna hipótesis, colócale una marca ( / ).
Cuando impliques alguna o algunas hipótesis, entonces termina de marcarlas o cruzarlas (X). Al final, todas las hipótesis deben estar cruzadas.
¿Cómo sabes que ya terminaste de hacer la demostración? Plantea dos preguntas o condiciones:
¿Lo que obtuviste es igual a la conclusión?
¿Implicaste todas las hipótesis?
Si las dos respuestas no son afirmativas, entonces no has terminado. Sigue adelante.
Si las dos respuestas son afirmativas, entonces has demostrado la validez del razonamiento.
Usa tres columnas; en la primera enumera todos los pasos del método, desde el paso 1; en la segunda especifica la regla usada (P o T) haciendo referencia al número de la hipótesis o del paso o pasos sobre los cuales estés trabajando y, en su caso, la implicación utilizada (tomada de la tabla III). En la tercera columna especifica la fórmula proposicional obtenida.
Paso
Regla
Fórmula proposicional
Es necesario que impliques todas las premisas o hipótesis.
Al terminar
Cuando se cumplan las dos condiciones puedes decir que el razonamiento es válido, que el argumento es válido, que todo corresponde a una implicación tautológica, que la conclusión se obtiene a partir de las hipótesis, que el argumento es consistente lógicamente; en fin, como lo digas es exactamente lo mismo: el razonamiento es válido.
Nota importante: ¿Qué pasa si llegas a una expresión igual a la conclusión, pero sin haber implicado todas las hipótesis? Simplemente el argumento no es válido, ya que debes cumplir las dos condiciones.
La explicación del MDPP está basada en lo expuesto por Tremblay en su libro Matemáticas discretas con aplicación a las ciencias de la computación.
Detalles y herramientas a usar
Es necesario que manejes adecuadamente tres tablas para aplicar el método (imprímelas):
Demuestra la validez del siguiente razonamiento usando el método de deducción paso a paso (MDPP).
Si Toluca gana el campeonato, entonces América no está en la final. Si América no está en la final, entonces León es eliminado. Si León es eliminado, entonces Pumas obtiene el campeonato. Si Toluca no gana el campeonato, entonces León es eliminado. Por lo tanto, Pumas obtiene el campeonato o León es eliminado.
1
Solución
Parece un trabalenguas, pero no lo es. Demuestra la validez del razonamiento mediante el método de deducción paso a paso MDPP. Procede a escribir la notación simbólica. Primero detecta las proposiciones atómicas:
A: Toluca gana el campeonato.
B: América está en la final.
D: León es eliminado.
E: Pumas obtiene el campeonato.
A continuación escribe las premisas o hipótesis:
H1: Si Toluca gana el campeonato, entonces América no está en la final (A → 7B).
H2: Si América no está en la final, entonces León es eliminado (7B → D).
H3: Si León es eliminado, entonces Pumas obtiene el campeonato (D → E).
H4: Si Toluca no gana el campeonato, entonces León es eliminado (7A → D).
Termina escribiendo la conclusión:
C: Pumas obtiene el campeonato o León es eliminado (E ∨ D).
Escribe la notación simbólica completa:
H1: A → 7B
H2: 7B → D
H3: D → E
H4: 7A → D
C: E ∨ D
Ya tienes todo en notación simbólica.
2
Aplicación del método
Paso
Regla
Fórmula proposicional
1
P, H1
A → 7B
2
P, H2
7B → D
3
T, 1, 2, I13
P → Q, Q → R P → R
A → 7B, 7B → D A → D
A → D
4
P, H3
D → E
5
T, 3, 4, I13
P → Q, Q → R P → R
A → D, D → E A → E
A → E
6
P, H4
7A → D
7
T, 5, Eq
7E → 7A
8
T, 7, 6, I13
P → Q, Q → R P → R
7E → 7A, 7A → D 7E → D
7E → D
9
T, 8, Eq
E ∨ D
3
Explicación del método
El MDPP requiere cierta habilidad para meter las hipótesis en algún orden. Tomando como referencia la hipótesis que hayas metido, a continuación introduce aquélla que te permita establecer alguna relación con lo que ya tienes. Todas las hipótesis deben intervenir en alguna implicación tautológica. Al final debes encontrar una expresión igual a la conclusión para que el razonamiento sea válido.
4
Ejemplo 2
Demuestra la validez del siguiente razonamiento usando el método de deducción paso a paso (MDPP).
Si estudio con ahínco, entonces no repruebo materias. Estudio con ahínco y practico un deporte. Repruebo materias o aprendo matemáticas. Por lo tanto, aprendo matemáticas.
1
Solución
Nuevamente parece un acertijo, pero no lo es. Procede a escribir la notación simbólica. Primero detecta las proposiciones atómicas.
A: Estudio con ahínco.
B: Repruebo materias.
D: Practico un deporte.
E: Aprendo matemáticas.
A continuación escribe las premisas o hipótesis:
H1: Si estudio con ahínco, entonces no repruebo materias (A → 7B).
H2: Estudio con ahínco y practico un deporte (A ∧ D).
H3: Repruebo materias o aprendo matemáticas (B ∨ E).
Termina escribiendo la conclusión:
C: Aprendo matemáticas (E).
Escribe la notación simbólica completa:
H1: A → 7B
H2: A ∧ D
H3: B ∨ E
C: E
Ya tienes todo en notación simbólica. Aplica el método.
2
Aplicación del método
Paso
Regla
Fórmula proposicional
1
P, H2
A ∧ D
2
T, 1, I1
P ∧ Q P
A ∧ D A
A
3
P, H1
A → 7B
4
T, 2, 3, I11
P, P → Q Q
A, A → 7B 7B
7B
5
P, H3
B ∨ E
6
T, 4, 5, I10
7P, P ∨ Q Q
7B, B ∨ E E
E
3
Explicación del método
No olvides verificar las dos condiciones y que existen varios caminos para llegar a la conclusión. Recuerda que las reglas de inferencia son criterios que sirven para demostrar la validez de un argumento.
4
Actividad 1. Sólo para superdotados como tú
Ahora seguirás el proceso del método de deducción paso a paso (MDPP) para demostrar la validez de un argumento. Selecciona la respuesta que te lleve a demostrar que el razonamiento es válido.
Autoevaluación 1. Arriésgate y gana
Es momento de que pongas a prueba lo que has aprendido hasta ahora. Completa las oraciones arrastrando las opciones del lado derecho a los espacios correspondientes. Al finalizar podrás conocer tu desempeño.
Actividad 2. Casi, casi una misión imposible
Ahora te presentamos un nuevo ejercicio para demostrar la validez de un razonamiento mediante el método de deducción paso a paso.
Completa las fórmulas proposicionales arrastrando las opciones del lado derecho a los espacios correspondientes. Al finalizar podrás conocer tu desempeño.
Fuentes de información
Bibliografía básica
Tremblay, J. y Manohar, R. (1996). Matemáticas discretas con aplicación a las ciencias de la computación. (R. Rangel, trad.). México: FI-UNAM/Compañía Editorial Continental.
Zaldívar, O. y Zaldívar, O. (2015). Estructuras discretas. Lógica proposicional y cálculo de predicados. Cuaderno de ejercicios (2.a ed.). México: FI-UNAM.
Bibliografía complementaria
Arenas, L. (1996). Lógica formal para informáticos. Madrid: Díaz de Santos.
Cuena, J. (1985). Lógica informática. Madrid: Alianza.
Garrido, M. (1991). Lógica simbólica (2.a ed.). Madrid: Tecnos.
Mendelson, E. (1997). Introduction to Mathematical Logic (4.a ed.). Londres: Chapman & Hall.
